#coding=utf8
__author__ = 'joey'

from math import log


# 1 收集数据: 假数据
def createDataSet():
    dataSet = [
                [1, 1, 'yes'],
                [1, 1, 'yes'],
                [1, 0, 'no'],
                [0, 1, 'no'],
                [0, 1, 'no']
              ]
    labels = ['no surfacing', 'flippers']
    return dataSet, labels

# 2 准备数据
# 2.1 计算香农熵, 参数为数据集
def calcShannonEnt(dataSet):
    # 获取样本个数
    numEntitis = len(dataSet)
    # 创建标签计数类, key: 标签 是否属于鱼类(yes or no) value: 标签 是否属于鱼类 (yes or no)的个数
    labelCounts = {}
    # 循环各个样本计算标签 是否是鱼类(yes or no)的个数
    for featVec in dataSet:
        # 获取当前的(yes or no)
        currentLabel = featVec[-1]
        # 累加当前样本的标签 是否是鱼类(yes or no)的个数, 默认获取为0
        labelCounts[currentLabel] = labelCounts.get(currentLabel, 0) + 1
    # 循环标签计数类的key, 循环labelCounts 等同于循环 labelCount.keys()
    # 根据ID3算法（http://zh.wikipedia.org/wiki/ID3%E7%AE%97%E6%B3%95）　计算样本熵值
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts.get(key)) / numEntitis
        shannonEnt -= prob * log(prob, 2)
    return shannonEnt

# 2.2 按照给定特征划分数据, 参数为数据集，划分数据集的特征索引，特征返回值
def splitDataSet(dataSet, axis, value):
    retDataSet = []
    for featVec in dataSet:
        # 当当前特征等于返回特征时
        if featVec[axis] == value:
            # 过滤掉axis位置的属性
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis + 1:])
            # 组装过滤后的数据集
            retDataSet.append(reducedFeatVec)
    return retDataSet

# 2.3 选择最好的数据划分方式
def chooseBestFeatureToSplit(dataSet):
    # 获取特征数
    numFeatures = len(dataSet[0]) - 1
    # 计算基础香农熵
    baseEntropy = calcShannonEnt(dataSet)
    # 最好的信息增益
    bestInfoGain = 0.0
    # 最好的特征值


